#include"BinaryTree.h"


//用先序序列创建二叉树
void BinaryTree::Deserialize(char* str)
{
	TreeNode* root = nullptr;
	if (str == nullptr)
	{
		return;
	}
	mroot = DeserializeDFS(str);
}
TreeNode* BinaryTree::DeserializeDFS(char*& str)
{
	if (str == nullptr || *str == '#')
	{
		++str;
		return nullptr;
	}
	else
	{
		int value = 0;
		while (*str != ',')
		{
			value = 10 * value + *str - '0';
			++str;
		}
		str++;
		TreeNode* p = new TreeNode(value);
		p->left = DeserializeDFS(str);
		p->right = DeserializeDFS(str);
		return p;
	}
}

//将二叉树转化成先序序列
char* BinaryTree::Serialize()
{
	if (mroot == nullptr)
	{
		return nullptr;
	}
	string str;
	SerializeDFS(mroot, str);
	char* res = new char[str.size() + 1];
	strcpy(res, str.c_str());
	return res;
}
void BinaryTree::SerializeDFS(TreeNode* root, string& arr)
{
	if (root == nullptr)
	{
		arr += '#';
	}
	else
	{
		arr += std::to_string(root->val);
		arr += ",";
		SerializeDFS(root->left, arr);
		SerializeDFS(root->right, arr);
	}
}

//之字形打印二叉树
vector<vector<int>> BinaryTree::Print()
{
	vector<vector<int>> res;
	if (mroot != nullptr)
	{
		stack<TreeNode*> sta1, sta2;
		sta1.push(mroot);
		while (!sta1.empty() || !sta2.empty())
		{
			vector<int> vec1, vec2;
			TreeNode* p = nullptr;
			while (!sta1.empty())
			{
				p = sta1.top(); sta1.pop();
				vec1.push_back(p->val);
				if (p->left != nullptr)
					sta2.push(p->left);
				if (p->right != nullptr)
					sta2.push(p->right);
			}
			if (!vec1.empty())
				res.push_back(vec1);


			while (!sta2.empty())
			{
				p = sta2.top(); sta2.pop();
				vec2.push_back(p->val);
				if (p->right != nullptr)
					sta1.push(p->right);
				if (p->left != nullptr)
					sta1.push(p->left);
			}
			if (!vec2.empty())
				res.push_back(vec2);
		}
	}
	return res;
}

void BinaryTree::ShowTwoVec(vector<vector<int>>& tvec)
{
	vector<vector<int>>::iterator tit = tvec.begin();
	vector<int>::iterator it;
	for (; tit != tvec.end(); tit++)
	{
		for (it = (*tit).begin(); it != (*tit).end(); it++)
		{
			cout << *it << " ";
		}
		cout << endl;
	}
}

//打印先序遍历

void BinaryTree::ShowBT()
{
	if (mroot == nullptr)
	{
		return;
	}
}